Everything about Circular Buffer totally explained
A
circular buffer or
ring buffer is a
data structure that uses a single, fixed-size
buffer as if it were connected end-to-end.
This structure lends itself easily to buffering
data streams.
Uses
A key advantage of a circular buffer is that it has a static size and elements need not be shuffled around when a portion of the buffer is used. This means that only new data is written to the buffer and the computational cost is independent of the length of the buffer.
For example, in implementing a
Transmission Control Protocol stack the windows used to hold the data can be circular buffers.
When the receiver acknowledges the reception of a packet then the amount of data acknowledged is used to advance the start of the buffer.
This allows the stack to restrict the amount of unacknowledged data by the transmitter.
(This is an example of when it isn't permitted for the start of the buffer to be overwritten.)
An example that could possibly use an overwriting circular buffer is with multimedia.
If the buffer is used as the bounded buffer in the
producer-consumer problem then it's probably desired for the producer (for example, an audio generator) to overwrite old data if the consumer (for example, the
sound card) is unable to momentarily keep up. Another example is the
digital waveguide synthesis method which uses circular buffers to efficiently simulate the sound of
vibrating strings or
wind instruments.
The "prized" attribute of a circular buffer is that it doesn't need to have its elements shuffled around when one is consumed.
(If a non-circular buffer were used then it would be necessary to shift all elements when one is consumed.)
In other words, the circular buffer is well suited as a
FIFO buffer while a standard, non-circular buffer is well suited as a
LIFO buffer.
How it works
A circular buffer first starts empty and of some predefined length.
For example, this is a 7-element buffer:
»
Assume that a 1 is written into the middle of the buffer (exact starting location doesn't matter in a circular buffer):
»
Then assume that two more elements are added — 2 & 3 — which get appended after the 1:
»
If two elements are then removed from the buffer then they come from the end.
The two elements removed, in this case, are 1 & 2 leaving the buffer with just a 3:
»
If the buffer has 6 elements added then it's completely full:
»
A consequence of the circular buffer is that when it's full then a subsequent write is performed then it starts overwriting the oldest data.
In this case, two more elements — A & B — are added and they
overwrite then 3 & 4:
»
Alternatively, the routines that manage the buffer could easily not allow data to be overwritten and return an error or raise an
exception.
Whether or not data is overwritten is up to the semantics of the buffer routines or the application using the circular buffer.
Finally, if after overwriting elements two elements are removed then what would be returned is
not 3 & 4 but 5 & 6 because A & B overwrote the 3 & the 4 yielding the buffer with:
»
Circular buffer mechanics
What isn't shown in the example above is the mechanics of how the circular buffer is managed.
Start / End Pointers
Generally, a circular buffer requires three
pointers:
- one to the actual buffer in memory
- one to point to the start of valid data
- one to point to the end of valid data
Alternatively, a fixed-length buffer with two integers to keep track of indices can be used in languages that don't have pointers.
Taking a couple of examples from above.
(While there are numerous ways to label the pointers and exact semantics can vary, this is one way to do it.)
This image shows a partially-full buffer:
»
This image shows a full buffer with two elements having been overwritten:
»
What to note about the second one is that after each element is overwritten then the start pointer is incremented as well.
Difficulties
Full / Empty Buffer Distinction
Some small disadvantage of relying on pointers or relative indices of the start and end of data is, that in the case the buffer is entirely full, both pointers pointing at the same element:
»
This is exactly the same situation as when the buffer is empty:
»
To solve this problem there are a number of solutions:
Always keep one byte open.
Use a fill count to distinguish the two cases.
Use read and write counts to get the fill count from.
Use absolute indices.
Always Keep One Byte Open
This simple solution always keeps one byte unallocated. A full buffer has at most 
